package 数组.非递减有序数组的平方;

import java.util.Arrays;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/4/19 14:56
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {-7,-3,2,3,11};
        sortedSquares2(array);
        System.out.println("sss");
    }

    //暴力解法
    public static int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }

    //双指针
    public static int[] sortedSquares2(int[] nums) {
        int n = nums.length;
        //ans数组利用pos下标从后向前放置元素，每次放置的就是较大的一位(原数组也是非递减有序的)
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }

}
